package BinaryTree;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

import BinaryTree.init.TreeNode;

public class lc107 {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> res1 = new ArrayList<>();
        Deque<TreeNode> que = new LinkedList<>();
        if (root == null) {
            return res1;
        }
        que.offerLast(root);
        while (!que.isEmpty()) {
            List<Integer> list = new ArrayList<>();
            int size = que.size();
            while (size > 0) {
                TreeNode tmpNode = que.peekFirst();
                list.add(que.pollFirst().val);
                if (tmpNode.left != null) que.offerLast(tmpNode.left);
                if (tmpNode.right != null) que.offerLast(tmpNode.right);

                size--;
            }
            res1.add(list);
        }
        List<List<Integer>> res2 = new ArrayList<>();
        for (int i = res1.size() - 1; i >= 0; i--) {
            res2.add(res1.get(i));
        }
        return res2;
    }
}
